/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-04-09
 * Time:13:13
 */
/**
 * 780. 到达终点
 *给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。
 * 从点 (x, y) 可以转换到 (x, x+y)  或者 (x+y, y)。
 * */
public class TestDemo {
    public static void main(String[] args) {
        System.out.println(reachingPoints(1, 1, 3, 5));
    }

    //正向递归会超时
    public static boolean reachingPoints1(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) {
            return false;
        }
        if (sx == tx && sy == ty) {
            return true;
        }
        boolean ans = reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sy + sx, tx, ty);
        return ans;
    }
    //给定的 (sx, sy)(sx,sy) 的数据范围为 [1, 10^9]（即均为正整数），且每次转换，
    // 只能将另外一维的数值累加到当前维，因此对于每一维的数值而言，随着转换次数的进行，
    // 呈（非严格）递增趋势，再结合起始值为正整数，可知在转换过程中均不会出现负数。
    //由此得知从 (tx, ty)到 (sx,sy) 的转换过程唯一确定：总是取较大数减去较小数来进行反推（
    // 否则会出现负数）。
    //但即使反向转换唯一确定，数据范围为 10^9，线性模拟仍会超时。
    //我们考虑将「相同操作的连续段转换动作」进行合并，在某次反向转换中，如果有 tx < ty，我们会
    // 将 (tx, ty)转换为 (tx, ty - tx)，若相减完仍有 tx < ty - tx，该操作会继续进行，
    // 得到 (tx, ty - 2 * tx)，直到不满足 tx < ty - k * tx，其中 k 为转换次数。
    //即对于一般性的情况而言，(tx, ty)中的较大数会一直消减到「与较小数的余数」为止。
    //
    public static boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy) {
            if (tx > ty) {
                tx = tx % ty;
            } else {
                ty = ty % tx;
            }
        }
        if (tx < sx || ty < sy) {
            return false;
        }
        return sx == tx ? (ty - sy) % tx == 0 : (tx - sx) % ty == 0;
    }
}